#include <iostream>
#include <string.h>
#include <math.h>
#include <map>
using namespace std;


struct tree{
	int x,y;
	bool operator < (const tree a)const{
		return x>a.x;
	}
};



int main(){
	int n,t,ans=0;
	cin>>n>>t;
//	map<tree,int> m;
	int a[n][n],dp[n][n];
	tree e[t];
	memset(dp,0,sizeof(dp));
	memset(a,0,sizeof(a));
	for(int i=0;i<t;i++){
		int x,y;
		cin>>x>>y;
		a[x-1][y-1] = 1;
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i > 0  &&  j > 0  &&  a[i][j] == 0  &&  dp[i-1][j-1] != 0){
				int num=dp[i-1][j-1];
				int size=1;
				for(int k=1;k<=num;k++){
					if(a[i-k][j] == 1  ||  a[i][j-k] == 1){
						break;
					}
					size++;
				}
				dp[i][j] = size;
			}
			else{
				if(a[i][j] != 1)
					dp[i][j] = 1;
			}
			ans = max(ans,dp[i][j]);
		}
	}
//	for(int i=0;i<n;i++){
//		for(int j=0;j<n;j++)
//			cout<<dp[i][j]<<" ";
//		cout<<endl;
//	}
	cout<<ans;
	return 0;
}
